class Solution:
    def getAllCombie(self, n, m):
        def next(stack, n1, n2, m1, m2):
            r = []
            # 放入左小
            if n1 > 0:
                stack.append('(')
                now = next(stack, n1 - 1, n2, m1, m2)
                for j in now:
                    r.append('(' + j)
                stack.pop(-1)
            # 放入右小
            if n2 > n1 and len(stack) > 0 and stack[-1] == '(':
                stack.pop(-1)
                now = next(stack, n1, n2 - 1, m1, m2)
                for j in now:
                    r.append(')' + j)
                stack.append('(')
            # 放入左大
            if m1 > 0:
                stack.append('{')
                now = next(stack, n1, n2, m1 - 1, m2)
                for j in now:
                    r.append('{' + j)
                stack.pop(-1)
            # 放入右大
            if m2 > m1 and len(stack) > 0 and stack[-1] == '{':
                stack.pop(-1)
                now = next(stack, n1, n2, m1, m2 - 1)
                for j in now:
                    r.append('}' + j)
                stack.append('{')
            # 结果为空时，即递归到最后了
            if len(r) == 0:
                return [""]
            return r

        if n < 0 or m < 0:
            return []
        return next([], n, n, m, m)


if __name__ == "__main__":
    n = -1
    m = 0
    so = Solution()
    r = so.getAllCombie(n, m)
    # r2 = "{}()(),{()}(),{()()},({})(),(){}(),(){()},()({}),()(){},{}(()),{(())},({}()),({()}),(({})),((){}),(()){}".split(",")
    # r2 = set(r2)
    # for i in r:
    #     if i not in r2:
    #         print(i)
    #     else:
    #         r2.remove(i)
    print(r)
    # print(r2)
